import java.util.*;
public class Leetcode {
}

//leetcode:17:电话号码的组合
class Solution1 {
    List<String> ret;
    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        if(digits.length() == 0){
            return ret;
        }
        //创建哈希表存储每个号码对应的字符
        Map<Character,String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        dfs(digits,map,0,new StringBuilder());
        return ret;
    }

    public void dfs(String digits,Map<Character,String> map,int index,StringBuilder path){
        //如果index走到了最后就将此时字符串的值放入表中
        if(index == digits.length()){
            ret.add(path.toString());
            return;
        }
        //按顺序获得号码
        char digit = digits.charAt(index);
        //通过获得的号码得到，这个号码对应的字符串
        String newdigits = map.get(digit);
        //遍历获得的字符串，让字符串的每个字符进行匹配
        for(int i = 0;i < newdigits.length();i++){
            //将字符放入字符串中
            path.append(newdigits.charAt(i));
            //获得下一个号码对应的字符串，重复上面的操作进行两个号码字符的匹配
            dfs(digits,map,index+1,path);
            //每匹配完一个就删除匹配完字符串的最后一个字符，回到原来的位置
            path.deleteCharAt(path.length()-1);
        }
    }
}

//leetcode:22:括号生成
class Solution2 {
    List<String> ret;
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        dfs(n,0,0,new StringBuilder());
        return ret;
    }

    public void dfs(int n,int x,int y,StringBuilder path){
        //如果字符串的长度等于2倍的n就将它放入表中
        if(path.length() == 2*n){
            ret.add(path.toString());
            return;
        }
        //从零开始左括号的数量要小于n才能放入
        if(x < n){
            path.append('(');
            //获得下一个要放入的括号
            dfs(n,x+1,y,path);
            //回溯，并移除字符串的最后一个元素，去另一个分支
            path.deleteCharAt(path.length()-1);
        }
        //如果想要放入右括号就要让右括号的个数要小于左括号的个数
        if(y < x){
            path.append(')');
            //获得下一个要放入的括号
            dfs(n,x,y+1,path);
            //回溯，并移除字符串的最后一个元素，去另一个分支
            path.deleteCharAt(path.length()-1);
        }
    }
}